// https://leetcode.cn/problems/letter-case-permutation/

// 题干：给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
//       返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

// 示例：输入：s = "a1b2"
//       输出：["a1b2", "a1B2", "A1b2", "A1B2"]

// 碎语：本题依旧是遍历一遍字符串，当遇到数字的时候跳过
//       当遇到字母的时候，再变大变小分类讨论即可

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    vector<string> res;
    string path;
public:
    vector<string> letterCasePermutation(string s)
    {
        dfs(s, 0);

        return res;
    }

    void dfs(string s, int pos)
    {
        if (pos == s.size())
        {
            res.push_back(path);
            return ;
        }

        if ('0' <= s[pos] && s[pos] <= '9')
        {
            path.push_back(s[pos]);
            dfs(s, pos + 1);
            path.pop_back();
        }
        else {
            // 先统一转化为小写
            s[pos] = tolower(s[pos]);

            path.push_back(s[pos]);
            dfs(s, pos + 1);
            path.pop_back(); // 小写情况

            s[pos] = toupper(s[pos]);
            path.push_back(s[pos]);
            dfs(s, pos + 1);
            path.pop_back(); // 大写情况
        }
    }
};

int main()
{
    Solution sol;
    string s = "a1b2";

    vector<string> index = sol.letterCasePermutation(s);
    for (const string& str : index){
        cout << str << endl;
    }

    return 0;
}